package offer.day32;

public class No56First_FindNumsAppearOnce {
    /*
     * 面试题56：数组中数字出现的次数
     * 题目一：数组中只出现一次的两个数字
     * 一个整型数组中除两个数字之外，其他数字都出现了两次。
     * 请写程序找出这两个只出现一次的庶长子。
     * 要求时间复杂度O(n),空间复杂度O(1).
     * 例如：输入数组{2，4，3，6，3，2，5，5}，因为只有4和6这两个数字只出现了一次，
     * 其他数字都出现了两次，所以输出4和6
     *
     * 思路：
     * 异或运算： 任何一个数字异或它自己都等于0
     * 所以我们可以从头到尾依次异或数组中的每一个数字，
     * 那么最终的结果刚好是只出现一次的数字，因为出现两次的数字全部在异或运算中抵消了
     *
     * 将数组分为两个子数组，
     * 在每个子数组中，包含一个只出现一次的数字，而其他数字都出现了两次
     * 若是能够这样拆分数组，那么按照上面的异或运算过程就能求出出现一次的数字
     *
     * 每个子数组都是从头开始依次进行异或运算，因为有两个数字肯定不一样，那么异或的结果一定不为0
     * 也就是说这个结果数字二进制表示中至少有一位为1
     * 在结果数字中找到第一个为1的位的位置，记为第N位。现在以第N位是不是1为标准将原数组分成两个子数组
     *
     * 第一个数组中每个数字的第N位都是1，第二个数组中每个数字的第N位都为0
     *
     * 现在已经将原数组分为两个子数组，每个子数组都包含一个只出现一次的数字
     * 出现两次的数字都已经抵消
     *
     * */
    public static void main(String[] args) {
        No56First_FindNumsAppearOnce f = new No56First_FindNumsAppearOnce();
        int[] array = {2,4,3,6,3,2,5,5};
        int num1 = 0;
        int num2 = 0;
        int[] num = f.FindNumsAppearOnce(array,num1,num2);
        System.out.println("数组中只出现一次的两个数字是："+num[0]+","+num[1]);
    }

    private int[] FindNumsAppearOnce(int[] array, int num1, int num2) {
        if(array==null||array.length==0) return null;

        int res=0;
        for(int i = 0;i < array.length;i++) {
            res ^= array[i];
        }
        int firstIndex=findFirstIndex(res);

        num1=num2=0;
        for(int i=0;i<array.length;i++){
            if(isBit1(array[i],firstIndex)){
                num1^=array[i];
            }else{
                num2^=array[i];
            }
        }
        int[] num={num1,num2};
        return num;
    }

    private boolean isBit1(int item,int firstIndex){
        boolean check=false;
        item=item>>firstIndex;
        if((item&1)==1){
            check=true;
        }
        return check;
    }

    /**
     * 返回从右往左第一个1
     * @param res
     * @return
     */
    private int findFirstIndex(int res) {
        int index=0;
        while((1&res)==0&&index<32){
            res=res>>1;
            index++;
        }
        return index;
    }


}
